package com.yxp.offer;

import com.yxp.middle.Problem1008;
import com.yxp.util.BuildTreeByBfs;
import com.yxp.util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : yang.xp
 * @date : 2021/8/27 9:34
 * @description : 剑指 Offer 34. 二叉树中和为某一值的路径
 */
public class Problem34 {

    private int preSum;
    private List<List<Integer>> resultList;

    public static void main(String[] args) {
        BuildTreeByBfs buildTreeByBfs = new BuildTreeByBfs();
        int[] numbers = new int[]{5, 4, 8, 11, 0, 13, 4, 7, 2, 0, 0, 5, 1};
        TreeNode treeNode = buildTreeByBfs.buildTree(numbers);
        Problem34 problem34 = new Problem34();
        System.out.println(problem34.pathSum(treeNode, 22));
    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        resultList = new ArrayList<>();
        List<Integer> integerList = new ArrayList<>();
        bfs(root, target, integerList);
        return resultList;
    }


    public void bfs(TreeNode treeNode, int target, List<Integer> integerList) {
        if (treeNode.left != null) {
            preSum += treeNode.val;
            integerList.add(treeNode.val);
            bfs(treeNode.left, target, integerList);
            bfs(treeNode.right, target, integerList);
        } else if (treeNode.right != null) {
            preSum += treeNode.val;
            integerList.add(treeNode.val);
            bfs(treeNode.left, target, integerList);
            bfs(treeNode.right, target, integerList);
        } else {
            if (preSum == target) {
                resultList.add(new ArrayList<>(integerList));
            } else {
                integerList.clear();
            }
            preSum = 0;
        }
    }
}
